import java.util.LinkedList;
import java.util.Queue;

public  class demo2 {
     static int []dx=new int[]{0,0,1,-1};
     static int []dy=new int[]{1,-1,0,0};
     static boolean[][] ret;
     static int  m=0;
  static    int n=0;
    public  static int numIslands(char[][] grid) {
         m=grid.length;
         n=grid[0].length;
        int sum=0;
        ret=new boolean[m][n];
        for(int i=0;i<m;i++){
            for (int j = 0; j <n ; j++) {
                if(grid[i][j]=='1'&& !ret[i][j]){
                    sum++;
                    dsf(grid,i,j);
                }
            }
        }
        return sum;
    }
    public static void dsf(char[][] grid,int x,int y){
        Queue<int[]>queue=new LinkedList<>();
        queue.add(new int[]{x,y});
        while (!queue.isEmpty()){
            int []arr= queue.poll();
            int a=arr[0];
            int b=arr[1];
            ret[a][b]=true;
            for(int i=0;i<4;i++){
                int c=a+dx[i];
                int d=b+dy[i];
                if(c>=0&&c<m&&d>=0&&d<n&&grid[c][d]=='1'&&!ret[c][d]){
                    ret[c][d]=true;
                    queue.add(new int[]{c,d});
                }
            }
        }
    }

    public static void main(String[] args) {
        char[][]grid={
                {'1','1','1','1','0'},
            {'1','1','0','1','0'},
            {'1','1','0','0','0'},
            {'0','0','0','0','0'}
        };
        System.out.println(numIslands(grid));
    }
}
